#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <glib-2.0/glib.h>
#include <glib.h> 
#include "network.h"
#include "vecinos.h"
#define min( a, b ) ( ((a) < (b)) ? (a) : (b) ) /*!< Funcion minimo */

struct s_network{

    GHashTable *nodes; /*!< Los nodos del network*/
    GHashTable *path; /*!< Para recuperar el camino */
};

int* flow_and_path(network n);

static void edge_free(gpointer ino){
	edge_destroy((edge) ino);
}

static void node_free(gpointer ino){
	node_destroy((node) ino);
}

/** Crea un nuevo network.

*/
network network_create(){
    network n = NULL;
    n = (network) malloc(sizeof(struct s_network));
    if (n == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    n -> nodes = g_hash_table_new_full(g_int_hash,g_int_equal,
                            free,node_free);
    n -> path = g_hash_table_new_full(g_int_hash,g_int_equal,
                            free,edge_free);
    return n;
}

/** Agrega los nodos y las aristas al network.
    \param n : Un network
    \param from : El vertice origen de la arista
    \param to : El vertice destino de la arista.
    \param cap : La capacidad de la arista.
    \pre
    <code> (n != NULL) </code>
    \return : void
*/
void network_add(network n, int from, int to, int cap){
    edge eg = NULL;
    node nd_from = NULL;
    node nd_to = NULL;
    int *key_from = NULL;
    int *key_to = NULL;
    
    assert(n != NULL);
    
    key_from = calloc(1,sizeof(int));
    key_to = calloc(1,sizeof(int));
    if (key_from == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    
    if (key_to == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    
    *key_from = from;
    *key_to = to;
    
    nd_from = (node) g_hash_table_lookup(n->nodes,key_from);
    nd_to = (node) g_hash_table_lookup(n->nodes,key_to);
    
    if (nd_from == NULL){
        nd_from = node_create(from);
        g_hash_table_insert (n->nodes,key_from,nd_from);
    }
    else
        free(key_from);
    
    eg = edge_create(from,to,cap);
    neighbour_add(node_neighbours(nd_from),eg);
    
    if (nd_to == NULL){
        nd_to = node_create(to);
        g_hash_table_insert (n->nodes,key_to,nd_to);
    }
    else
        free(key_to);
}

/** Destruye un network.
    \param n : Un network.
    \pre
    <code> (n != NULL) </code>
    \return : NULL
*/
network network_destroy(network n){
    assert(n != NULL);
    assert(n->nodes != NULL);
    assert(n->path != NULL);

    g_hash_table_destroy (n->nodes);
    g_hash_table_destroy (n->path);
    free(n);
    return NULL;
}
/** Realiza un recorrido BFS en el network y devuelve un arreglo con el
camino recorrido y el flujo del mismo.
    \pre
    <code> (n != NULL) </code>
    \param n : Un network.
    \return : Si el camino existe devuelve el camino, sino NULL.
*/
int* network_bfs(network n){
    GQueue *q = NULL;
    node node_first = NULL;
    node node_s = NULL;
    node next_node = NULL;
    edge current_edge = NULL;
    neighbours neighbours_first = NULL;
    int i = 0;
    int to_node = 0;
    int* camino;
    int *key_s = NULL;
    int *key_edge = NULL;
    int *node_number = NULL;
    assert(n!=NULL);
    
    key_s = calloc(1,sizeof(int));
    if (key_s == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    *key_s = 0;
    
    node_number = calloc(1,sizeof(int));
    if (node_number == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    
    node_s = (node) g_hash_table_lookup(n->nodes,key_s);
    
    q = g_queue_new();
    node_visit(node_s);
    g_queue_push_tail(q,node_s);
    
    while(!g_queue_is_empty(q)){
        node_first = (node) g_queue_peek_head(q);
        
        /* Guardo los vecinos del primer nodo de la cola*/
        neighbours_first = node_neighbours(node_first);
        
        /* Esto se hace para cada uno de los vecinos del vertice*/
        for(i=1;i<=neighbours_size(neighbours_first);i++){
            current_edge = neighbours_current(neighbours_first);
            to_node = edge_to(current_edge);
            *node_number = to_node;
            next_node = (node)g_hash_table_lookup(n->nodes,node_number);
            
            /* Guardo el registro de quien agrego a next_node*/
            key_edge = calloc(1,sizeof(int));
            *key_edge = edge_to(current_edge);
            g_hash_table_insert(n->path,key_edge,current_edge);
                
            /* Paso al siguiente vecino*/
            neighbours_next(neighbours_first);
            
            if (!node_visited(next_node)){
                node_visit(next_node);
                g_queue_push_tail(q,next_node);
                if (node_name(next_node) == 1)
                    break;
            }
        }
        g_queue_pop_head(q);
    }
    g_queue_free(q);
    free(node_number);
    free(key_s);
	camino = flow_and_path(n);
    return camino;
}

/** Funcion auxiliar del BFS que calcula el camino
    \pre
    <code> (n != NULL) </code>
    \param n : Un network.
    \return : Si el camino existe devuelve el camino, sino NULL.
*/
int* flow_and_path(network n){
    int i = 3;
    int flow = 2147483647; 
    int path_size = g_hash_table_size(n->nodes);
    edge current_edge = NULL;
    int *node_number = NULL;
    int* camino = NULL;
    
    node_number = calloc(1,sizeof(int));
    if (node_number == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    
    camino = (int*)calloc(path_size+1,sizeof(int));
    if (camino == NULL){
        printf("Memoria insuficiente\n");
        exit(1);
    }
    
    camino[2] = 1;
    *node_number = 1;
    
    while( *node_number != 0){
        current_edge = (edge) g_hash_table_lookup(n->path,node_number);
        if (current_edge == NULL){
                free(camino);
                return NULL;
        }
        else{
            *node_number = edge_from(current_edge);
            camino[i] = *node_number;
            i++;
            flow = min(flow,edge_cap(current_edge)); 
        }
    }
    camino[0] = i-1;
    camino[1] = flow;
    free(node_number);
    return camino;
}

